package LinkedList;
//面试题 02.07. 链表相交
//给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
//图示两个链表在节点 c1 开始相交：
public class intersection_of_two_linked_lists_lcci {
    class ListNode{
        int val;
        ListNode next;
        public ListNode(int val){
            this.val=val;
        }
    }
    /*输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
      输出：Intersected at '2'
      解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
      从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
      在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
     */
    // 不能只单纯地去判断两个节点相等 要判断后面一系列也相等 所以最好是从尾部遍历起

    /**
     * 思路过程
     * 链表 A 为 [0,3,9,1,2,4]
     * 链表 B 为   [3,2,4]
     * 链表 A 为 [0,3,9,1,2,4]
     * 链表 B 为       [3,2,4]
     * 首先想到的是：如果能一起向后走就好了，但这里因为得比较 所以如果要定义两个指针的话，就得去让指针A移动一次，则指针B得遍历一遍
     *      很明显这样子不行，浪费时间
     * 但是这里要求的是：后面一系列的值都相等，那么在这个情况下
     * 只有链表A和链表B对齐，后面的一系列才可能全都相等，如果不对齐的话，即使链表A和链表B的3是先相等的，但是因为后面连数量都不相等，所以一定不相等！
     * 所以最终的思路是：1.先去将那个长的去移动指针，使得两个链表指向对齐位置，然后一起移动，直到有一个相等，则返回
     * 长链表移动多少呢？移动长的size-短的size个单位
     */
    //todo:链表移动技巧
    //1.4-->2-->3-->5
    //在模拟时，用size是几，此时是几去描述
    //在刚开始时 此时是2，size是1,1写在-->下面 笔指向2，然后去判断条件
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA=headA;
        ListNode curB=headB;
        int sizeA=0;
        int sizeB=0;
        //直接将这两个遍历到尾部,得到长度
        while (curA!=null){
            curA=curA.next;
            sizeA++;
        }
        while (curB!=null){
            curB=curB.next;
            sizeB++;
        }
        //得到长度后复原
        curA=headA;
        curB=headB;
        // 这里因为不知道哪个长/哪个短了 所以方法1：用if else 去弄，但是会代码冗余，即if(a>b)xx else if(b>a)xx这样子
        // todo：方法2（推荐） 以后遇到这种不知道哪个大的 可以先去用判断条件 使得 A一定是大的，b一定是小的
        //这个方法过后，A就一定是长链表了 curA就是它的头
        if(sizeA<sizeB){
            //交换size和sizeb
            int a=sizeA;
            sizeA=sizeB;
            sizeB=a;
            //交换cura和b，使得curA为长链表的头
            ListNode node=curA;
            curA=curB;
            curB=node;
        }
        int step=sizeA-sizeB;//所以这里一定是a-b
        for (int i = 0; i < step; i++) {
            curA=curA.next; //这里一定是a先去走
        }
        //现在来到了同一水平
        while (curA!=null){
            //todo：注意：这里使用的是curA==curB 也就是说这里直接去判断了链表 而不是去判断val
            if(curA==curB){
                return curA;
            }
            curA=curA.next;
            curB=curB.next;
        }
        return null;
    }
}
